But where did it all begin? The first, that was, so constraint satisfaction problems were

developed in a PhD thesis which looked at line drawings. Computer vision where you had

a video camera and would understand the picture in real time weren't doable at the time. But

they said, well, let's do a partial problem. Let's look at these black and white line drawings

and try to understand them. And for this one you probably see a block in front of you that

looks nice, it's kind of like a three dimensional Tetris block. But here there's a problem.

If you look at it in one way, then this is a kind of a cube where you've bitten out a

little cube on one corner. Another way, and it flips back and forth, is where you've kind

of added a little skewed cube instead of a corner. Now the question is which of these

line drawings make sense? Think about the pictures by Moets Escher and which of them

don't? Which of the edges are convex or concave? And so the idea here is that you look at the

intersections and always want to know is this convex or concave? Think about this one. Is

this convex or concave? Does it come towards you or away from you? And what you realize

if you think about it is that the state, say, of this intersection of lines or corner of

a block has something to do with this one. If you kind of have a concave way of thinking

of it, then this line at the beginning is concave if and only if the line at the end

is also concave. There you have constraints. And that's really what Waltz realized. So

what you have, so you have to make a couple of assumptions, right? You have all of these

blocks. They don't have any cracks, which would be kind of lines that end somewhere,

and they don't have any shadows. If you have shadows, the whole thing don't work. So you

make things easy. And you only have vertices here that are three-faced. And then what you

want to do is all the inner edges you want to label with convex as this one. You put

a little plus on it. And for the border ones, you give them directions, right? So that if

you travel in the right direction, the left-hand side is always empty space. That thing. And

we call this here a consistent labeling. And you can ask yourselves, well, if I give you

a line drawing, can I make a consistent labeling? And the observation is that consistent labeling

things always correspond to actual objects. And then you kind of look at the application

and then you see that there's only 18 legal kinds of junctions. If this is an edge that

– let's look at this. You can have kind of Y-formed edges where you have a concave

edge pointing to you, away from you. And you can have something which has space over here,

but then it has to be ordered. So if we have a concave thing, then this has to be ordered

left to right and a couple of variations of this. Actually, you get these here by turning.

So this is something where you actually look at lots of examples. And if you then introduce

the constraints for every one of these junctions that the labelings at both ends of the edges

have – or the lines have to match up, then you have a consistency problem. And you would

actually – come on, go back. You basically need to do these assignments. And if you can

have a consistent labeling, then you can actually find all these blocks. And – yes?

In the previous slide? Yes. This one?

It's the second block. It is undecidable. What do you mean undecidable? It's a finite

problem, so I can solve it in finite time. Because we can also see it like three – three

– a small cube at the corner. Yes. There's two – here – so the test,

whether the algorithm actually works, is whether you get two consistent labelings. Okay? And

indeed, you can basically start out with plus plus plus and then kind of propagate saying

there must be a plus here, plus here, plus there, and then you look up the edges and

then you can kind of spread the whole thing over. That will actually lead to two consistent

labelings. Meaning you can see two objects that just from the line drawing look the same.

But if you have no consistent line labeling, then you cannot build the object. That's

the prediction of the Waltz model. Anything – any line – any line drawing that has

a consistent labeling actually can exist in the world. And if you have two consistent

line labelings, you have two different objects. Does that answer your question? Maybe rephrase.